Википедия
кограф, или дополнительно сводимый граф, или свободный от P граф — это граф, который можно получить из графа с единственной вершиной K путём операций дополнения и объединения графов . Таким образом, семейство кографов — это наименьший класс графов, содержащий K и замкнутый относительно дополнения и объединения.
Кографы открывались независимо несколькими авторами, начиная с 1970-х годов. Самые ранние упоминания можно найти у Янга, Лерчса, Зайнше и Самнера. Эти графы назывались D*-графами, наследственными графами Дейси (после работы Джеймса Дейси [James C. Dacey, Jr.] об . Смотрите работу Самнера) и графы с двумя потомками Барлета и Ури.
Смотрите книгу Брандштедта, Ли и Шпинрада, где кографы рассмотрены более детально, включая факты, приведённые здесь.